#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>

//5.5 结构体设计
#define TRUE 1
#define FALSE 0
typedef int STATUS;
#define MAXSIZE 20
#define GOODSNUM 5
#define MAXFLIP 3 //最大邻域个数
#define LIMIT 10  //背包体积
#define INTERATION 800  //遗传代数
typedef char GOODSNAME[MAXSIZE];
typedef struct GOODS
{
    GOODSNAME name;
    int volume;
    int value;
}GOODS,*GOD;
GOD map;
typedef struct BAG
{
    int status[GOODSNUM];
    int alreadyvolume;
    int alreadyvalue;
}BAG;

//5.6.1 计算当前背包的总重量和总价值
void CouBagData(GOD map,BAG *bag)
{
    int nowvolume=0,nowvalue=0;
    for(int i=0;i<GOODSNUM;i++)
    {
        if(bag->status[i]==1)
        {
            nowvalue+=map[i].value;
            nowvolume+=map[i].volume;
        }
    }
    bag->alreadyvalue=nowvalue;
    bag->alreadyvolume=nowvolume;
    if(bag->alreadyvolume>LIMIT)
    {
        bag->alreadyvalue=-1;
    }
}

//5.6.2 复制背包到新背包
void CopyBag(BAG *bag,BAG *newbag)
{
    int i;
    for(i=0;i<GOODSNUM;i++)
    {
        newbag->status[i]=bag->status[i];
    }
    newbag->alreadyvalue=bag->alreadyvalue;
    newbag->alreadyvolume=bag->alreadyvolume;
}

//5.6.3 定义当前可派生出状态数
#define NEIGHBORNUM pow(2,GOODSNUM)

//5.6.4 随机交换(类似于染色体交叉变异)
void Shaking_Procdure(GOD map,BAG *bag)
{
    int num=rand()%(GOODSNUM)+3;
    for(int i=0;i<num;i++)
    {
        if(bag->status[i]==0)
        {
            bag->status[i]=1;
        }
        else
        {
            bag->status[i]=0;
        }
    }
    CouBagData(map,bag);
}

//5.6.5 清除所有书包近邻状态
void ClearAllTraBag(BAG *neighbors)
{
    free(neighbors);
}

//5.6.6 书包近邻详细规则类型定义
int ExpandBag(BAG* neighbors,int type)
{
    int i,j,k=-1,temp,count=0;
    if(type==1)
    {
        for(i=0;i<GOODSNUM;i++)
        {
            if(neighbors[i].status[i]==1)     neighbors[i].status[i]=0;
            else                              neighbors[i].status[i]=1;
            count++;
        }
    }
    else if(type==2)
    {
        for(i=0;i<GOODSNUM;i++)
        {
            for(j=i+1;j<GOODSNUM;j++)
            {
                k=k+1;
                if(neighbors[k].status[i]==1)
                {
                    neighbors[k].status[i]=0;
                }
                else
                {
                    neighbors[k].status[i]=1;
                }

                if(neighbors[k].status[j]==1)
                {
                    neighbors[k].status[j]=0;
                }
                else
                {
                    neighbors[k].status[j]=1;
                }
                count++;
            }
        }
    }
    else
    {
        for(i=0;i<GOODSNUM;i++)
        {
            if(i<3)
            {
                temp=neighbors[i].status[i];
                neighbors[i].status[i]=neighbors[i].status[GOODSNUM+i-3];
                neighbors[i].status[GOODSNUM+i-3]=temp;
            }
            else
            {
                temp=neighbors[i].status[i];
                neighbors[i].status[i]=neighbors[i].status[i-3];
                neighbors[i].status[i-3]=temp;
            }
            count++;
        }
    }
}

//5.6.6 书包近邻所有情况
BAG* ExpandTraBag(GOD map,BAG *bag)
{
    int i,flip=1,count=0;        //循环控制变量，城市位置变量
    BAG *neighbors;              //派生所有最近邻路径
    neighbors=(BAG *)malloc(sizeof(BAG)*NEIGHBORNUM);   //分配足够存储派生旅行商路径的连续存储单元
    for(i=0;i<NEIGHBORNUM;i++)                 //复制路径
    {
        CopyBag(bag,&neighbors[i]);            //复制NEIGHBORNUM次当前路径
    }
    while(flip<MAXFLIP)
    {
        CouBagData(map,bag);
        count=ExpandBag(neighbors,flip);
        for(i=0;i<count;i++)
        {
            CouBagData(map,&neighbors[i]);
            if(neighbors[i].alreadyvalue>bag->alreadyvalue)
            {
                CopyBag(&neighbors[i],bag);
            }
        }
        flip=flip+1;
    }
    return neighbors;
}

//5.6.7 0-1背包问题求解
void SearchResultMain(GOD map,BAG *initbag,BAG *resbag)
{
    BAG *neighbors;                 //所有派生的书包状态
    CopyBag(initbag,resbag);
    STATUS flag=FALSE;              //默认当前最大   
    CouBagData(map,resbag);
    neighbors=ExpandTraBag(map,resbag);
    for(int i=0;i<INTERATION;i++)      // UPDATE:染色体遗传代数
    {
        ClearAllTraBag(neighbors);
        Shaking_Procdure(map,initbag);  //UPDATE:染色体交叉变异
        neighbors=ExpandTraBag(map,initbag);
        if(initbag->alreadyvalue > resbag->alreadyvalue)
        {
            CopyBag(initbag,resbag);
        }
    }
    CopyBag(resbag,initbag);
}

//5.6.8 0-1背包问题初始化
void InitTraBag(GOD map,BAG *start)
{
    int i,j=0,n,k;
    BAG temp;
    for(i=0;i<GOODSNUM;i++)
    {
        start->status[i]=0;
    }
    int nowvolume=32767;         //初始体积无限大
    CopyBag(start,&temp);
    //n=rand()%(GOODSNUM);
    while(nowvolume>LIMIT)
    {
        for(i=0;i<GOODSNUM;i++)
        {
            j=rand()%(GOODSNUM);
            k=rand()%(GOODSNUM);
            temp.status[j]=1;
            temp.status[k]=0;
        }
        CouBagData(map,&temp);
        nowvolume=temp.alreadyvolume;
    }
    CopyBag(&temp,start);
}

//5.6.9 书包状态展示
void PriBag(GOD map,BAG bag)
{
    printf("当前在书包内元素:");
    for(int i=0;i<GOODSNUM;i++)
    {
        if(bag.status[i]==1)    printf("%s ",map[i].name);
    }
    printf("\n当前不在书包内元素:");
    for(int i=0;i<GOODSNUM;i++)
    {
        if(bag.status[i]==0)     printf("%s ",map[i].name);
    }
    printf("\n当前书包体积:%d",bag.alreadyvolume);
    printf("\n当前书包价值:%d\n",bag.alreadyvalue);
}


//5.6.M 主程序
void main()
{
    int i;
    BAG bag,bagres;
    GOODS map[GOODSNUM]={{"a",2,6},{"b",2,3},{"c",6,5},{"d",5,4},{"e",4,6}};
    for(int i=0;i<10;i++)                          //同局部最优算法，延时多次计算产生不同结果
    {
        InitTraBag(map,&bag);                          //初始化背包
        printf("Init Status:\n");                      //显示背包状态
        PriBag(map,bag);
        SearchResultMain(map,&bag,&bagres);               //最大价值背包
        printf("\nResult Status:\n");                      //显示背包状态
        PriBag(map,bagres);
        printf("=========================\n");
        Sleep(2000);
    }
}